#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 328. 奇偶链表.py
@time: 2022/2/18 16:50
@desc: https://leetcode-cn.com/problems/odd-even-linked-list/
> 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

1. 迭代，Ot(N), Os(N)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        dummyOdd = ListNode()
        dummyEven = ListNode()
        op, ep = dummyOdd, dummyEven
        i = 1
        p = head
        while p:
            next = p.next
            # 记得断链
            p.next = None
            if not i%2==0:
                op.next = p
                op = op.next
            else:
                ep.next = p
                ep = ep.next
            p = next
            i += 1
        op.next = dummyEven.next
        return dummyOdd.next

if __name__ == '__main__':
    head = ListNode(1, next=ListNode(2, next=ListNode(3, next=ListNode(4, next=ListNode(5)))))
    res = Solution().oddEvenList(head)
    print(res)